The present invention relates generally to packet switch for forwarding (inclusive of switching, transmitting and transferring unless specified otherwise) a fixed length packet, which is applied to a broadband switch, a cross-connect switch and a router, and more particularly to a packet switch taking a packet reading (or outputting) control method (algorithm) of dynamically determining a connection.
In an ATM (Asynchronous Transfer Mode) switch or an ATM transmission device for forwarding a fixed-length packet known as a cell, on the occasion of actualizing a GFR (Guaranteed Frame Rate) function defined as a minimum cell rate (MCR) guarantee function, a conventional scheduling method for guaranteeing a minimum cell rate may be exemplified by a cell reading (or outputting) control method such as a WRR (Weighted Round Robin) method and a WFQ (Weighted Fair Queue) method.
For example, according to an article (SSE98-192: [“Development of GFR Processing Circuit Having Band Sharing Effect”] (Document 1)) by Switching System Workshop in The Japanese Electronic Information Communications Association, the minimum cell rate (MCR) is guaranteed by adopting the WRR method considering whether or not there exists a cell in queue according to a virtual channel VC.
According to this type of WRR-based cell reading method, the minimum cell rate of each VC is reflected in a weight ratio, whereby the minimum cell rate can be guaranteed and further an extra band can be allocated based on the weight ratio.
Further, according to [Round Robin Control System and Method] (Document 2) disclosed in Japanese Patent Application Laying-Open Publication No.11-239151], there is proposed a scheduling method for guaranteeing the minimum cell rate and trying a restriction based on a peak cell rate (PCR) by providing a memory stored with a minimum band cell count of the cells that should be read out (or output) for a unit time with respect to each VC and a (peak cell rate-minimum cell rate) cell count.
Moreover, according to [Band Shared Circuit] (Document 3) disclosed in Japanese Patent Application Laying-Open Publication No.11-191780, what is proposed therein is a method of guaranteeing the minimum cell rate and actualizing a strict PCR interval restriction by adding a restriction function of restricting, after reading the cell per connection (corresponding to VC), the read-out of a next cell of the relevant connection till a time given by [1/PCR] corresponding to an inverse number of PCR in linkage with the above cell read-out.
In the examples of the prior arts described above, according to the WRR-based reading method disclosed in the document 1, a table (or counter) weighted based on MCR per VC is set beforehand, and the cell is read out in accordance with this table. In this method, however, only the MCR-based band allocation can be executed, and hence, if schemed to accommodate the VC in which a ratio of MCR to PCR differs on a band shared unit, the efficiency decreases remarkably, or the PCR restriction can not be kept.
A more specific explanation will be given with the assumption that, for example, as shown in FIG. 1(A), two active VCs (VC#1, VC#2) exist. Note that the active VC is a VC where the cell exists in a corresponding queue (buffer memory).
In this VC set example, in a case (1) where the cell rate does not absolutely exceed PCR, PCR of VC#2 is restricted by 4 Mbps (b/s), and consequently PCR of VC#1 becomes 2 Mbps, with the result that the corresponding cell can be read only when less than original PCR (5 Mbps). Further, in a case (2) where the cell of VC#1 is read at PCR, PCR of VC#1 is 5 Mbps, which means that VC#2 exhibiting doubled MCR shows PCR of 10 Mbps well over PCR of VC#2.
Thus, there arises a problem that the PCR restriction and the read-out with the high efficiency are incompatible with each other under on the WRR read-out control.
What can be considered to obviate this problem is an architecture of an ATM switch ATM-SW, wherein a PCR shaper (peak cell rate restriction unit) SHP is, as shown in FIG. 2, provided at a rear stage of a WRR (Weighted Round Robin) (MCR guaranty) read-out control unit CNT. With this architecture, it is feasible to read out the cell at the high efficiency as in the case (2), and besides the PCR restriction can be attained by the PCR shaper.
According to this method for solution, however, the PCR shaper also requires an individual VC buffer BUF, and it is therefore inevitable that a hardware quantity increases to a large extent. Further, the cell rate restriction area is segmented into two sub-areas, resulting in a decline of efficiency.
Hence, a method of integrating and executing the MCR guaranty read-out and the PCR restriction in one area is effective in terms of reducing the hardware quantity and integrating the cell rate restriction sub-areas.
The ATM switch ATM-SW disclosed in the document 2 described above takes a scheduling method of trying the MCR guaranty and the PCR restriction by use of a counter memory in the same area (see FIG. 3).
This method, however, has an error of timing for initializing the counter, and it can be therefore presumed that this method is incapable of actualizing even the guaranty of the minimum cell rate, much less the PCR restriction. Supposing that an optimum initialization timing is taken, this method is simple enough to restrict a cell count of the cells read out for a predetermined unit time, and hence it is inevitable that there occurs a traffic burst corresponding to processing of a counter thereof (see FIG. 4(A)).
What can be considered as a method of obviating this traffic burst is that a read-out interval restriction counter is, as disclosed in the document 3 given above, provided for every VC, and a read-out cell interval is restricted in each VC so that a read-out rate is PCR or under (see FIG. 4(B)). Target items such as the reduction in the hardware quantity, the MCR guaranty, the impartial band allocation based on MCR and the strict PCR restriction can be actualized by adopting the system architecture disclosed in the document 3.
The method in the document 3 does not, however, account for priority control when a cell read-out conflict occurs at the same slot, and is therefore incapable of reading out the cells at a high efficiency, resulting in a decrease in throughput. Namely, there might occur a conflict controllable so that the cells of a plurality of VCs can be read out at a certain slot because of handling VCs having arbitrary MCR and PCR (see FIG. 5).
In such a case, the number of cells readable at one slot is “1,” and hence the scheduling control for selecting one of the plurality of VCs is needed. If this selection is executed based on Round Robin and on a static reading algorithm involving a selection of a VC having a larger MCR, he throughput might decline due to the selection in an improper reading sequence.
For example, as shown in FIG. 1(B), it is assumed that there are five active VCs (VC#1 , . . . , VC#5). MCR of VC#1 is 4 Mbps, and each of MCRs of other virtual channels VC#2˜VC#5 is 1 Mbps. Further, PCR of each VC is 10 Mbps for a total cell rate 20 Mbps, and each VC therefore requires a 2-slot PCR interval (slot interval) as a PCR restriction.
Under this condition, if trying to actualize impartial MCR read-out, there may be provided a mechanism for providing an MCR counter of which a value is proportional the MCR value, decrementing the counter value by [1] each time the cell is read out, and getting the relevant VC ruled out of the read-out target when the counter value comes to [0]. Further, when the value of each of the MCR counters of all the active VCs becomes [0], the MCR counter is reset.
In this example, when the read-out control based on Round Robin is carried out, as shown in FIG. 6, the read-out conflict between VC#1 and VC#3 occurs at the third slot from the start. During this conflict, the process is based on Round Robin in this example, and therefore the read-out priority is given not to VC#1 of which the cell has already been read out once but to VC#3 with the cell that is not yet read out. Similarly, in the case of the cell read-out conflict between VC#1 and VC#5, the cell of VC#1 is read out later on, and hence eventually the second cell of VC#1 is read out at the sixth slot to which Round Robin makes one cycle.
Moreover, at this point of time, the value of each of the MCR counters of VC#2˜VC#5 becomes [0], so that the cell readable VC is only VC#1. Hence, the cell of the VC#1 is read out at the sixth slot onwards. The PCR interval of VC#1 is, however, [2], and therefore the cells can not be read out consecutively. This leads to an occurrence of free slot, and a decline of throughput is therefore inevitable.
Further, supposing that a next read-out timing is set earlier corresponding to such a degree that the cell read-out of VC#1 is shifted backward (forwards the future in time) to a slot, a read-out time series becomes as shown in FIG. 7, whereby the free slot disappears with an enhanced throughput. While on the other hand, however, there might be a possibility in which the traffic burst remarkably increases, and this causes the same problem as in the method in the document 2.
On the other hand, if the cell read-out is executed not by Round Robin but by the algorithm for giving the priority to VC having a larger MCR as VC#1 has, the read-out time series becomes as shown in FIG. 8 in the case of the example shown in FIG. 1(B), wherein the conditions of the PCR restriction, CDV (Cell Delay Variation) and the throughput can be all satisfied. In an example as shown in FIG. 1(C), however, the read-out time series becomes as shown in FIG. 9, and it follows that the throughput declines.
Thus, the read-out control adopting the static reading algorithm has a problem that a pattern with declined performance invariably exists in a environment where there can be schemed an infinite number of VC accommodation patterns with PCR and MCR that differ per VC. Now, the reason why this sort of problem arises will be examined.
To start with, an emphasis is put on the examples shown in FIGS. 6 and 9 where the free slot occurs. A point common to these examples is that when the conflict occurs, the cell read-outs of the VCs where there are larger number of cells that should be read out at one cycle, i.e., the MCR counters have larger remaining values, are to be executed later on. Hence, there are eventually left only the VCs in which the MCR counters have the larger values, with the result that the free slots occurs due to the PCR restrictions of the VCs.
Namely, it may be considered that what is required is not the static cell reading algorithm but a cell reading algorithm for dynamically determining a cell read-out VC with reference to the present value of the MCR counter that is decremented each time the cell is read out. A problem still exists in the way of simply selecting the virtual channel VC having a larger MCR counter value.
For instance, as shown in FIG. 1(D), an example where the two active VCs exist is put into contemplation. When giving the priority to the VC having the larger MCR counter value, the read-out cell time series becomes as shown in FIG. 10. To be more specific, the cells of VC#1 having the larger MCR counter value are consecutively read out from the start up to the eighth slot, and at the ninth slot a first cell of VC#2 is read out. Until the cells for the MCR counter value of VC#2 are read out after the cells of VC#1 have been read out at the tenth and eleventh slots, however, it can be understood that the free slots occur, and the throughput declines.